Iterative DFS uses an explicit stack to precisely control the traversal, simulating the call stack used in recursion.

  • The core idea is to manage the exploration frontier using a LIFO (Last-In, First-Out) stack, which perfectly mimics the behavior of recursive calls.
  • When a node `u` is popped, it's processed. We then iterate through its neighbors in reverse order and push the unvisited ones onto the stack.
  • Using reversed() is a key detail: it ensures the iterative version visits nodes in the same order as a standard recursive DFS.
  • The check if u in visited: continue is crucial. Since a node might be pushed onto the stack multiple times by different parents, this ensures we only process each node once.
def dfs_iter(G, s):
visited, parent = set(), {s: None}
stack = [s]
while stack:
u = stack.pop()
if u in visited:
continue
visited.add(u)
for w in reversed(G[u]): # reversed to mimic recursion
if w not in visited:
parent[w] = u if w not in parent else parent[w]
stack.append(w)
return parent, visited